/**
 * 
 */
package leetCode;

import java.util.Stack;

/**
 * @author zhongfang
 *
 */
public class ConvertSortedArraytoBinarySearchTree {
	 public class TreeNode {
		      int val;
		      TreeNode left;
		      TreeNode right;
		      TreeNode(int x) { val = x; }
		  }
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0){
            return null;
        }
        TreeNode[] nodes=new TreeNode[nums.length];
        for(int i=0;i<nums.length;i++){
            nodes[i]=new TreeNode(nums[i]);
        }
        Stack<Integer> stack=new Stack<>();
        stack.push(0);
        stack.push(nums.length-1);
        while(!stack.isEmpty()){
            int right=stack.pop();
            int left=stack.pop();
            int mid=left+(right-left)/2;
            TreeNode curNode=nodes[mid];
            if(mid>left){
                curNode.left=nodes[left+(mid-1-left)/2];
                stack.push(left);
                stack.push(mid-1);
            }
            if(mid<right){
                curNode.right=nodes[mid+1+(right-mid-1)/2];
                stack.push(mid+1);
                stack.push(right);
            }
        }
        return nodes[(nums.length-1)/2];
    }
    private static void printTree(TreeNode node){
    	if(node==null)
    		return;
    	System.out.println(node.val);
    	printTree(node.left);
    	printTree(node.right);
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ConvertSortedArraytoBinarySearchTree arraytoBinarySearchTree=new ConvertSortedArraytoBinarySearchTree();
		int[] t={1,3};
		printTree(arraytoBinarySearchTree.sortedArrayToBST(t));
	}

}
